package 复习.博客2.递归和回溯;

public class 岛屿数量 {
    public int solve (char[][] grid) {
        // write code here
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if(grid[i][j] == '1'){
                    count++;
                    backstacking(grid,i,j);
                }
            }
        }
        return count;
    }

    public void backstacking(char[][] frid,int i,int j){
        if(frid[i][j] == '1'){
            frid[i][j] = '0';
        }
        if(i - 1 >= 0 && frid[i - 1][j] == '1'){
            backstacking(frid,i - 1,j);
        }
        if(i + 1 < frid.length && frid[i + 1][j] == '1'){
            backstacking(frid,i + 1,j);
        }
        if(j - 1 >= 0 && frid[i][j - 1] == '1'){
            backstacking(frid,i,j - 1);
        }
        if(j + 1 < frid[0].length && frid[i][j + 1] == '1'){
            backstacking(frid,i,j + 1);
        }
    }
}

/*
 public int solve (char[][] grid) {
        // write code here
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if(grid[i][j] == '1'){
                    count++;
                    backstackinig(grid,i,j);
                }
            }
        }
        return  count;
    }

    public void backstackinig(char[][] frid,int i,int j){
        if(frid[i][j] == '1'){
            frid[i][j] = '0';
        }
        if(i - 1 >= 0 && frid[i - 1][j] == '1'){
            backstackinig(frid,i - 1,j);
        }
        if(i + 1 < frid.length && frid[i + 1][j] == '1'){
            backstackinig(frid,i + 1,j);
        }
        if(j - 1 >= 0 && frid[i][j - 1] == '1'){
            backstackinig(frid,i,j - 1);
        }
        if(j + 1 < frid[0].length && frid[i][j + 1] == '1'){
            backstackinig(frid,i,j + 1);
        }
    }
 */